class Solution
{
public:
    int minimumChanges(string s, int k)
    {
        int n = s.size();

        auto operationCount = [&](int begin, int end)
        {
            int len = end - begin;
            int minOp = len / 2;
            for (int step = len - 1; step > 0; --step)
            {
                if (len % step != 0)
                {
                    continue;
                }
                int op = 0;
                int sliceLen = len / step; // 切片长度
                for (int start = 0; start < step; ++start)
                {
                    for (int i = 0; i < sliceLen / 2; ++i)
                    {
                        if (s[begin + start + i * step] != s[begin + start + (sliceLen - i - 1) * step])
                        {
                            op++;
                        }
                    }
                }
                minOp = min(minOp, op);
            }
            return minOp;
        };

        vector<vector<int>> dp(n + 1, vector<int>(k + 1, -1)); // dp[i][j] 表示将s[0:i]分割成j个"半回文串"的最小操作数, -1表示无法分割
        dp[0][0] = 0;

        for (int i = 1; i <= n; ++i)
        {
            for (int prev = 0; prev < i - 1; ++prev) // 半回文串的长度至少为2
            {
                int op = operationCount(prev, i);
                for (int j = 0; j < k; ++j)
                {
                    if (dp[prev][j] == -1)
                    {
                        continue;
                    }
                    if (dp[i][j + 1] == -1)
                    {
                        dp[i][j + 1] = dp[prev][j] + op;
                    }
                    else
                    {
                        dp[i][j + 1] = min(dp[i][j + 1], dp[prev][j] + op);
                    }
                }
            }
        }
        return dp[n][k];
    }
};